#include <iostream>
using namespace std;

/*
设计一个表示链表的类型 LinkList，让它支持下面这些操作。
Group 1
LinkList l;           创建一个空链表

Group 2
l.addAtIndex(1, 13);  在链表的第一个参数位置，插入第二个参数
l.addAtHead(10);      在表头位置插入元素 10
l.addAtTail(11);      在表尾位置插入元素 11

Group 3
l.get(1);             获取链表指定位置的值，位置从 0 开始
l.print();            打印链表所有元素

Group 4
l.deleteAtIndex(0);   删除链表位置 0 的元素

Group 5
l.hasCycle();         判断链表中是否存在循环
*/

class Node {
public:
  // 节点里保存的值
  int value;
  // 这个节点的下一个节点的位置
  Node * next;

  Node(int v, Node *pn) {
    value = v;
    next = pn;
  }
};

class LinkList {
public:
  Node * head; // 表头的节点的位置
  int size;    // 记录链表中的元素个数

  // 构造函数
  // LinkList l;
  LinkList() {
    head = nullptr;
    size = 0;
  }

  // 在链表的 pos 位置，插入值 value。
  // 表头的位置是 0
  // 0     1     2     3     4
  // 11 -> 12 -> 13 -> 14 -> 15
  //        ^
  //       12 -> 20 -> 13 ->
  // addAtIndex(2, 20)
  // 11 -> 12 -> 20 -> 13 -> 14 -> 15
  void addAtIndex(int pos, int value) {
    // 1. 要先确定 pos 合法
    // 负数不合法、>  size 的不合法
    if (pos < 0 || pos > size) {
      cout << "Invalid pos: " << pos << endl;
      return;
    }

    // 2. 基于 value 创建节点
    Node *pNode = new Node(value, nullptr);
    ++size;
    
    // 3. 把新建的节点插入到正确位置
    if (head == nullptr) {
      head = pNode;
      return;
    }
    else {
      // 先找到 pos - 1 的位置
      int i = 0;
      Node *tmp = head;
      while (i < pos - 1) {
        tmp = tmp->next;
        ++i;
      }

      // tmp 要插入位置的前一个位置
      pNode->next = tmp->next;
      tmp->next = pNode;
    }

    return;
  }

  // 直接在表头插入元素 value
  void addAtHead(int value) {
    addAtIndex(0, value);
  }

  // 直接在标尾插入元素 value
  void addAtTail(int value) {
    // addAtIndex(size, value);
  }

  /*
  vhead
  0              3
                 vl
  1 -> 3 -> 3 -> 1
       ^mid
       1 -> 3 -> 3 -> nullptr
                      ^mid 


  0         2
            vl
  1 -> 3 -> 1 -> nullptr
       ^mid

       1 -> 3 -> nullptr
                 ^mid

  1. 求出中间节点的位置 mid
  2. 从 mid 到链表的表尾，把链表逆序
  3. 比较链表中 0 ~ mid, mid ~ nullptr 对应位置的值是否相当
  4. 还原链表
  */
  bool isPalindrome() {
    
  }

  

  Node *getNode(int pos) {
    if (head == nullptr || pos < 0 || pos > size - 1) {
      return nullptr;
    }

    int i = 0;
    Node *p = head;
    while (i < pos) {
      ++i;
      p = p->next;
    }

    return p;
  }

  // 从 h 指向的节点开始，逆序之后的链表
  Node *reverse(Node *h) {
    Node *currH = h;

    // ...
    return currH;
  }

  // 对整个链表逆序
  void reverse() {
    head = reverse(head);
  }
};
